home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / cmds / flex / dist / nfa.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-10-19  |  16.9 KB  |  714 lines
  1. /* nfa - NFA construction routines */
  2.  
  3. /*
  4.  * Copyright (c) 1989 The Regents of the University of California.
  5.  * All rights reserved.
  6.  *
  7.  * This code is derived from software contributed to Berkeley by
  8.  * Vern Paxson.
  9.  * 
  10.  * The United States Government has rights in this work pursuant to
  11.  * contract no. DE-AC03-76SF00098 between the United States Department of
  12.  * Energy and the University of California.
  13.  *
  14.  * Redistribution and use in source and binary forms are permitted
  15.  * provided that the above copyright notice and this paragraph are
  16.  * duplicated in all such forms and that any documentation,
  17.  * advertising materials, and other materials related to such
  18.  * distribution and use acknowledge that the software was developed
  19.  * by the University of California, Berkeley.  The name of the
  20.  * University may not be used to endorse or promote products derived
  21.  * from this software without specific prior written permission.
  22.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  23.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  24.  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  25.  */
  26.  
  27. #ifndef lint
  28.  
  29. static char copyright[] =
  30.     "@(#) Copyright (c) 1989 The Regents of the University of California.\n";
  31. static char CR_continuation[] = "@(#) All rights reserved.\n";
  32.  
  33. static char rcsid[] =
  34.     "@(#) $Header: nfa.c,v 2.0 89/06/20 15:50:05 vern Locked $ (LBL)";
  35.  
  36. #endif
  37.  
  38. #include "flexdef.h"
  39.  
  40. /* add_accept - add an accepting state to a machine
  41.  *
  42.  * synopsis
  43.  *
  44.  *   add_accept( mach, accepting_number );
  45.  *
  46.  * accepting_number becomes mach's accepting number.
  47.  */
  48.  
  49. add_accept( mach, accepting_number )
  50. int mach;
  51.  
  52.     {
  53.     /* hang the accepting number off an epsilon state.  if it is associated
  54.      * with a state that has a non-epsilon out-transition, then the state
  55.      * will accept BEFORE it makes that transition, i.e., one character
  56.      * too soon
  57.      */
  58.  
  59.     if ( transchar[finalst[mach]] == SYM_EPSILON )
  60.     accptnum[finalst[mach]] = accepting_number;
  61.  
  62.     else
  63.     {
  64.     int astate = mkstate( SYM_EPSILON );
  65.     accptnum[astate] = accepting_number;
  66.     mach = link_machines( mach, astate );
  67.     }
  68.     }
  69.  
  70.  
  71. /* copysingl - make a given number of copies of a singleton machine
  72.  *
  73.  * synopsis
  74.  *
  75.  *   newsng = copysingl( singl, num );
  76.  *
  77.  *     newsng - a new singleton composed of num copies of singl
  78.  *     singl  - a singleton machine
  79.  *     num    - the number of copies of singl to be present in newsng
  80.  */
  81.  
  82. int copysingl( singl, num )
  83. int singl, num;
  84.  
  85.     {
  86.     int copy, i;
  87.  
  88.     copy = mkstate( SYM_EPSILON );
  89.  
  90.     for ( i = 1; i <= num; ++i )
  91.     copy = link_machines( copy, dupmachine( singl ) );
  92.  
  93.     return ( copy );
  94.     }
  95.  
  96.  
  97. /* dumpnfa - debugging routine to write out an nfa
  98.  *
  99.  * synopsis
  100.  *    int state1;
  101.  *    dumpnfa( state1 );
  102.  */
  103.  
  104. dumpnfa( state1 )
  105. int state1;
  106.  
  107.     {
  108.     int sym, tsp1, tsp2, anum, ns;
  109.  
  110.     fprintf( stderr, "\n\n********** beginning dump of nfa with start state %d\n",
  111.          state1 );
  112.  
  113.     /* we probably should loop starting at firstst[state1] and going to
  114.      * lastst[state1], but they're not maintained properly when we "or"
  115.      * all of the rules together.  So we use our knowledge that the machine
  116.      * starts at state 1 and ends at lastnfa.
  117.      */
  118.  
  119.     /* for ( ns = firstst[state1]; ns <= lastst[state1]; ++ns ) */
  120.     for ( ns = 1; ns <= lastnfa; ++ns )
  121.     {
  122.     fprintf( stderr, "state # %4d\t", ns );
  123.  
  124.     sym = transchar[ns];
  125.     tsp1 = trans1[ns];
  126.     tsp2 = trans2[ns];
  127.     anum = accptnum[ns];
  128.  
  129.     fprintf( stderr, "%3d:  %4d, %4d", sym, tsp1, tsp2 );
  130.  
  131.     if ( anum != NIL )
  132.         fprintf( stderr, "  [%d]", anum );
  133.  
  134.     fprintf( stderr, "\n" );
  135.     }
  136.  
  137.     fprintf( stderr, "********** end of dump\n" );
  138.     }
  139.  
  140.  
  141. /* dupmachine - make a duplicate of a given machine
  142.  *
  143.  * synopsis
  144.  *
  145.  *   copy = dupmachine( mach );
  146.  *
  147.  *     copy - holds duplicate of mach
  148.  *     mach - machine to be duplicated
  149.  *
  150.  * note that the copy of mach is NOT an exact duplicate; rather, all the
  151.  * transition states values are adjusted so that the copy is self-contained,
  152.  * as the original should have been.
  153.  *
  154.  * also note that the original MUST be contiguous, with its low and high
  155.  * states accessible by the arrays firstst and lastst
  156.  */
  157.  
  158. int dupmachine( mach )
  159. int mach;
  160.  
  161.     {
  162.     int i, init, state_offset;
  163.     int state = 0;
  164.     int last = lastst[mach];
  165.  
  166.     for ( i = firstst[mach]; i <= last; ++i )
  167.     {
  168.     state = mkstate( transchar[i] );
  169.  
  170.     if ( trans1[i] != NO_TRANSITION )
  171.         {
  172.         mkxtion( finalst[state], trans1[i] + state - i );
  173.  
  174.         if ( transchar[i] == SYM_EPSILON && trans2[i] != NO_TRANSITION )
  175.         mkxtion( finalst[state], trans2[i] + state - i );
  176.         }
  177.  
  178.     accptnum[state] = accptnum[i];
  179.     }
  180.  
  181.     if ( state == 0 )
  182.     flexfatal( "empty machine in dupmachine()" );
  183.  
  184.     state_offset = state - i + 1;
  185.  
  186.     init = mach + state_offset;
  187.     firstst[init] = firstst[mach] + state_offset;
  188.     finalst[init] = finalst[mach] + state_offset;
  189.     lastst[init] = lastst[mach] + state_offset;
  190.  
  191.     return ( init );
  192.     }
  193.  
  194. /* finish_rule - finish up the processing for a rule
  195.  *
  196.  * synopsis
  197.  *
  198.  *   finish_rule( mach, variable_trail_rule, headcnt, trailcnt );
  199.  *
  200.  * An accepting number is added to the given machine.  If variable_trail_rule
  201.  * is true then the rule has trailing context and both the head and trail
  202.  * are variable size.  Otherwise if headcnt or trailcnt is non-zero then
  203.  * the machine recognizes a pattern with trailing context and headcnt is
  204.  * the number of characters in the matched part of the pattern, or zero
  205.  * if the matched part has variable length.  trailcnt is the number of
  206.  * trailing context characters in the pattern, or zero if the trailing
  207.  * context has variable length.
  208.  */
  209.  
  210. finish_rule( mach, variable_trail_rule, headcnt, trailcnt )
  211. int mach, variable_trail_rule, headcnt, trailcnt;
  212.  
  213.     {
  214.     add_accept( mach, num_rules );
  215.  
  216.     /* we did this in new_rule(), but it often gets the wrong
  217.      * number because we do it before we start parsing the current rule
  218.      */
  219.     rule_linenum[num_rules] = linenum;
  220.  
  221.     fprintf( temp_action_file, "case %d:\n", num_rules );
  222.  
  223.     if ( variable_trail_rule )
  224.     {
  225.     rule_type[num_rules] = RULE_VARIABLE;
  226.  
  227.     if ( performance_report )
  228.         fprintf( stderr, "Variable trailing context rule at line %d\n",
  229.              rule_linenum[num_rules] );
  230.  
  231.     variable_trailing_context_rules = true;
  232.     }
  233.  
  234.     else
  235.     {
  236.     rule_type[num_rules] = RULE_NORMAL;
  237.  
  238.     if ( headcnt > 0 || trailcnt > 0 )
  239.         {
  240.         /* do trailing context magic to not match the trailing characters */
  241.         char *scanner_cp = "yy_c_buf_p = yy_cp";
  242.         char *scanner_bp = "yy_bp";
  243.  
  244.         fprintf( temp_action_file,
  245.     "*yy_cp = yy_hold_char; /* undo effects of setting up yytext */\n" );
  246.  
  247.         if ( headcnt > 0 )
  248.         {
  249.         if ( headcnt > 0 )
  250.             fprintf( temp_action_file, "%s = %s + %d;\n",
  251.                  scanner_cp, scanner_bp, headcnt );
  252.  
  253.         else
  254.             fprintf( temp_action_file, "%s = %s;\n",
  255.                  scanner_cp, scanner_bp );
  256.         }
  257.  
  258.         else
  259.         fprintf( temp_action_file,
  260.              "%s -= %d;\n", scanner_cp, trailcnt );
  261.     
  262.         fprintf( temp_action_file,
  263.              "YY_DO_BEFORE_ACTION; /* set up yytext again */\n" );
  264.         }
  265.     }
  266.  
  267.     line_directive_out( temp_action_file );
  268.     }
  269.  
  270.  
  271. /* link_machines - connect two machines together
  272.  *
  273.  * synopsis
  274.  *
  275.  *   new = link_machines( first, last );
  276.  *
  277.  *     new    - a machine constructed by connecting first to last
  278.  *     first  - the machine whose successor is to be last
  279.  *     last   - the machine whose predecessor is to be first
  280.  *
  281.  * note: this routine concatenates the machine first with the machine
  282.  *  last to produce a machine new which will pattern-match first first
  283.  *  and then last, and will fail if either of the sub-patterns fails.
  284.  *  FIRST is set to new by the operation.  last is unmolested.
  285.  */
  286.  
  287. int link_machines( first, last )
  288. int first, last;
  289.  
  290.     {
  291.     if ( first == NIL )
  292.     return ( last );
  293.  
  294.     else if ( last == NIL )
  295.     return ( first );
  296.  
  297.     else
  298.     {
  299.     mkxtion( finalst[first], last );
  300.     finalst[first] = finalst[last];
  301.     lastst[first] = max( lastst[first], lastst[last] );
  302.     firstst[first] = min( firstst[first], firstst[last] );
  303.  
  304.     return ( first );
  305.     }
  306.     }
  307.  
  308.  
  309. /* mark_beginning_as_normal - mark each "beginning" state in a machine
  310.  *                            as being a "normal" (i.e., not trailing context-
  311.  *                            associated) states
  312.  *
  313.  * synopsis
  314.  *
  315.  *   mark_beginning_as_normal( mach )
  316.  *
  317.  *     mach - machine to mark
  318.  *
  319.  * The "beginning" states are the epsilon closure of the first state
  320.  */
  321.  
  322. mark_beginning_as_normal( mach )
  323. register int mach;
  324.  
  325.     {
  326.     switch ( state_type[mach] )
  327.     {
  328.     case STATE_NORMAL:
  329.         /* oh, we've already visited here */
  330.         return;
  331.  
  332.     case STATE_TRAILING_CONTEXT:
  333.         state_type[mach] = STATE_NORMAL;
  334.  
  335.         if ( transchar[mach] == SYM_EPSILON )
  336.         {
  337.         if ( trans1[mach] != NO_TRANSITION )
  338.             mark_beginning_as_normal( trans1[mach] );
  339.  
  340.         if ( trans2[mach] != NO_TRANSITION )
  341.             mark_beginning_as_normal( trans2[mach] );
  342.         }
  343.         break;
  344.  
  345.     default:
  346.         flexerror( "bad state type in mark_beginning_as_normal()" );
  347.         break;
  348.     }
  349.     }
  350.  
  351.  
  352. /* mkbranch - make a machine that branches to two machines
  353.  *
  354.  * synopsis
  355.  *
  356.  *   branch = mkbranch( first, second );
  357.  *
  358.  *     branch - a machine which matches either first's pattern or second's
  359.  *     first, second - machines whose patterns are to be or'ed (the | operator)
  360.  *
  361.  * note that first and second are NEITHER destroyed by the operation.  Also,
  362.  * the resulting machine CANNOT be used with any other "mk" operation except
  363.  * more mkbranch's.  Compare with mkor()
  364.  */
  365.  
  366. int mkbranch( first, second )
  367. int first, second;
  368.  
  369.     {
  370.     int eps;
  371.  
  372.     if ( first == NO_TRANSITION )
  373.     return ( second );
  374.  
  375.     else if ( second == NO_TRANSITION )
  376.     return ( first );
  377.  
  378.     eps = mkstate( SYM_EPSILON );
  379.  
  380.     mkxtion( eps, first );
  381.     mkxtion( eps, second );
  382.  
  383.     return ( eps );
  384.     }
  385.  
  386.  
  387. /* mkclos - convert a machine into a closure
  388.  *
  389.  * synopsis
  390.  *   new = mkclos( state );
  391.  *
  392.  *     new - a new state which matches the closure of "state"
  393.  */
  394.  
  395. int mkclos( state )
  396. int state;
  397.  
  398.     {
  399.     return ( mkopt( mkposcl( state ) ) );
  400.     }
  401.  
  402.  
  403. /* mkopt - make a machine optional
  404.  *
  405.  * synopsis
  406.  *
  407.  *   new = mkopt( mach );
  408.  *
  409.  *     new  - a machine which optionally matches whatever mach matched
  410.  *     mach - the machine to make optional
  411.  *
  412.  * notes:
  413.  *     1. mach must be the last machine created
  414.  *     2. mach is destroyed by the call
  415.  */
  416.  
  417. int mkopt( mach )
  418. int mach;
  419.  
  420.     {
  421.     int eps;
  422.  
  423.     if ( ! SUPER_FREE_EPSILON(finalst[mach]) )
  424.     {
  425.     eps = mkstate( SYM_EPSILON );
  426.     mach = link_machines( mach, eps );
  427.     }
  428.  
  429.     /* can't skimp on the following if FREE_EPSILON(mach) is true because
  430.      * some state interior to "mach" might point back to the beginning
  431.      * for a closure
  432.      */
  433.     eps = mkstate( SYM_EPSILON );
  434.     mach = link_machines( eps, mach );
  435.  
  436.     mkxtion( mach, finalst[mach] );
  437.  
  438.     return ( mach );
  439.     }
  440.  
  441.  
  442. /* mkor - make a machine that matches either one of two machines
  443.  *
  444.  * synopsis
  445.  *
  446.  *   new = mkor( first, second );
  447.  *
  448.  *     new - a machine which matches either first's pattern or second's
  449.  *     first, second - machines whose patterns are to be or'ed (the | operator)
  450.  *
  451.  * note that first and second are both destroyed by the operation
  452.  * the code is rather convoluted because an attempt is made to minimize
  453.  * the number of epsilon states needed
  454.  */
  455.  
  456. int mkor( first, second )
  457. int first, second;
  458.  
  459.     {
  460.     int eps, orend;
  461.  
  462.     if ( first == NIL )
  463.     return ( second );
  464.  
  465.     else if ( second == NIL )
  466.     return ( first );
  467.  
  468.     else
  469.     {
  470.     /* see comment in mkopt() about why we can't use the first state
  471.      * of "first" or "second" if they satisfy "FREE_EPSILON"
  472.      */
  473.     eps = mkstate( SYM_EPSILON );
  474.  
  475.     first = link_machines( eps, first );
  476.  
  477.     mkxtion( first, second );
  478.  
  479.     if ( SUPER_FREE_EPSILON(finalst[first]) &&
  480.          accptnum[finalst[first]] == NIL )
  481.         {
  482.         orend = finalst[first];
  483.         mkxtion( finalst[second], orend );
  484.         }
  485.  
  486.     else if ( SUPER_FREE_EPSILON(finalst[second]) &&
  487.           accptnum[finalst[second]] == NIL )
  488.         {
  489.         orend = finalst[second];
  490.         mkxtion( finalst[first], orend );
  491.         }
  492.  
  493.     else
  494.         {
  495.         eps = mkstate( SYM_EPSILON );
  496.  
  497.         first = link_machines( first, eps );
  498.         orend = finalst[first];
  499.  
  500.         mkxtion( finalst[second], orend );
  501.         }
  502.     }
  503.  
  504.     finalst[first] = orend;
  505.     return ( first );
  506.     }
  507.  
  508.  
  509. /* mkposcl - convert a machine into a positive closure
  510.  *
  511.  * synopsis
  512.  *   new = mkposcl( state );
  513.  *
  514.  *    new - a machine matching the positive closure of "state"
  515.  */
  516.  
  517. int mkposcl( state )
  518. int state;
  519.  
  520.     {
  521.     int eps;
  522.  
  523.     if ( SUPER_FREE_EPSILON(finalst[state]) )
  524.     {
  525.     mkxtion( finalst[state], state );
  526.     return ( state );
  527.     }
  528.  
  529.     else
  530.     {
  531.     eps = mkstate( SYM_EPSILON );
  532.     mkxtion( eps, state );
  533.     return ( link_machines( state, eps ) );
  534.     }
  535.     }
  536.  
  537.  
  538. /* mkrep - make a replicated machine
  539.  *
  540.  * synopsis
  541.  *   new = mkrep( mach, lb, ub );
  542.  *
  543.  *    new - a machine that matches whatever "mach" matched from "lb"
  544.  *          number of times to "ub" number of times
  545.  *
  546.  * note
  547.  *   if "ub" is INFINITY then "new" matches "lb" or more occurrences of "mach"
  548.  */
  549.  
  550. int mkrep( mach, lb, ub )
  551. int mach, lb, ub;
  552.  
  553.     {
  554.     int base_mach, tail, copy, i;
  555.  
  556.     base_mach = copysingl( mach, lb - 1 );
  557.  
  558.     if ( ub == INFINITY )
  559.     {
  560.     copy = dupmachine( mach );
  561.     mach = link_machines( mach,
  562.                   link_machines( base_mach, mkclos( copy ) ) );
  563.     }
  564.  
  565.     else
  566.     {
  567.     tail = mkstate( SYM_EPSILON );
  568.  
  569.     for ( i = lb; i < ub; ++i )
  570.         {
  571.         copy = dupmachine( mach );
  572.         tail = mkopt( link_machines( copy, tail ) );
  573.         }
  574.  
  575.     mach = link_machines( mach, link_machines( base_mach, tail ) );
  576.     }
  577.  
  578.     return ( mach );
  579.     }
  580.  
  581.  
  582. /* mkstate - create a state with a transition on a given symbol
  583.  *
  584.  * synopsis
  585.  *
  586.  *   state = mkstate( sym );
  587.  *
  588.  *     state - a new state matching sym
  589.  *     sym   - the symbol the new state is to have an out-transition on
  590.  *
  591.  * note that this routine makes new states in ascending order through the
  592.  * state array (and increments LASTNFA accordingly).  The routine DUPMACHINE
  593.  * relies on machines being made in ascending order and that they are
  594.  * CONTIGUOUS.  Change it and you will have to rewrite DUPMACHINE (kludge
  595.  * that it admittedly is)
  596.  */
  597.  
  598. int mkstate( sym )
  599. int sym;
  600.  
  601.     {
  602.     if ( ++lastnfa >= current_mns )
  603.     {
  604.     if ( (current_mns += MNS_INCREMENT) >= MAXIMUM_MNS )
  605.         lerrif( "input rules are too complicated (>= %d NFA states)",
  606.             current_mns );
  607.     
  608.     ++num_reallocs;
  609.  
  610.     firstst = reallocate_integer_array( firstst, current_mns );
  611.     lastst = reallocate_integer_array( lastst, current_mns );
  612.     finalst = reallocate_integer_array( finalst, current_mns );
  613.     transchar = reallocate_integer_array( transchar, current_mns );
  614.     trans1 = reallocate_integer_array( trans1, current_mns );
  615.     trans2 = reallocate_integer_array( trans2, current_mns );
  616.     accptnum = reallocate_integer_array( accptnum, current_mns );
  617.     assoc_rule = reallocate_integer_array( assoc_rule, current_mns );
  618.     state_type = reallocate_integer_array( state_type, current_mns );
  619.     }
  620.  
  621.     firstst[lastnfa] = lastnfa;
  622.     finalst[lastnfa] = lastnfa;
  623.     lastst[lastnfa] = lastnfa;
  624.     transchar[lastnfa] = sym;
  625.     trans1[lastnfa] = NO_TRANSITION;
  626.     trans2[lastnfa] = NO_TRANSITION;
  627.     accptnum[lastnfa] = NIL;
  628.     assoc_rule[lastnfa] = num_rules;
  629.     state_type[lastnfa] = current_state_type;
  630.  
  631.     /* fix up equivalence classes base on this transition.  Note that any
  632.      * character which has its own transition gets its own equivalence class.
  633.      * Thus only characters which are only in character classes have a chance
  634.      * at being in the same equivalence class.  E.g. "a|b" puts 'a' and 'b'
  635.      * into two different equivalence classes.  "[ab]" puts them in the same
  636.      * equivalence class (barring other differences elsewhere in the input).
  637.      */
  638.  
  639.     if ( sym < 0 )
  640.     {
  641.     /* we don't have to update the equivalence classes since that was
  642.      * already done when the ccl was created for the first time
  643.      */
  644.     }
  645.  
  646.     else if ( sym == SYM_EPSILON )
  647.     ++numeps;
  648.  
  649.     else
  650.     {
  651.     if ( useecs )
  652.         mkechar( sym, nextecm, ecgroup );
  653.     }
  654.  
  655.     return ( lastnfa );
  656.     }
  657.  
  658.  
  659. /* mkxtion - make a transition from one state to another
  660.  *
  661.  * synopsis
  662.  *
  663.  *   mkxtion( statefrom, stateto );
  664.  *
  665.  *     statefrom - the state from which the transition is to be made
  666.  *     stateto   - the state to which the transition is to be made
  667.  */
  668.  
  669. mkxtion( statefrom, stateto )
  670. int statefrom, stateto;
  671.  
  672.     {
  673.     if ( trans1[statefrom] == NO_TRANSITION )
  674.     trans1[statefrom] = stateto;
  675.  
  676.     else if ( (transchar[statefrom] != SYM_EPSILON) ||
  677.           (trans2[statefrom] != NO_TRANSITION) )
  678.     flexfatal( "found too many transitions in mkxtion()" );
  679.  
  680.     else
  681.     { /* second out-transition for an epsilon state */
  682.     ++eps2;
  683.     trans2[statefrom] = stateto;
  684.     }
  685.     }
  686.  
  687. /* new_rule - initialize for a new rule
  688.  *
  689.  * synopsis
  690.  *
  691.  *   new_rule();
  692.  *
  693.  * the global num_rules is incremented and the any corresponding dynamic
  694.  * arrays (such as rule_type[]) are grown as needed.
  695.  */
  696.  
  697. new_rule()
  698.  
  699.     {
  700.     if ( ++num_rules >= current_max_rules )
  701.     {
  702.     ++num_reallocs;
  703.     current_max_rules += MAX_RULES_INCREMENT;
  704.     rule_type = reallocate_integer_array( rule_type, current_max_rules );
  705.     rule_linenum =
  706.         reallocate_integer_array( rule_linenum, current_max_rules );
  707.     }
  708.  
  709.     if ( num_rules > MAX_RULE )
  710.     lerrif( "too many rules (> %d)!", MAX_RULE );
  711.  
  712.     rule_linenum[num_rules] = linenum;
  713.     }
  714.